1. Field of the Invention
The present invention generally relates to electronic circuits and, more specifically, to the protection of data contained in an integrated circuit against an extraction thereof, after an analysis of the circuit power consumption during calculations involving the data. The present invention more specifically relates to the protection of modular exponentiation algorithms. Such algorithms are used, for example, in smart cards or secure components for ciphering, signing, or putting in common data by means of a secret quantity of the chip, for example, in a DSA, RSA, or Diffie-Hellman algorithm).
2. Discussion of the Related Art
FIG. 1 is a schematic block diagram of a simplified architecture of an integrated circuit 1, for example, of a smart card, of the type to which the present invention applies. Circuit 1 comprises a central processing unit 11 (CPU) associated with one or several memories 12 (MEM) among which generally at least one element of non-volatile storage of a secret digital quantity (for example, a confidential code), and an input/output circuit 13 (I/O) enabling data exchange with the outside of circuit 1. The different elements communicate over one or several internal data, address, and control buses 14. Most often, several memories 12 among which at least one RAM and one non-volatile program storage memory are provided in the circuit.
Among possible attacks performed by persons attempting to fraudulently obtain confidential data from chip 1, the present invention applies to so-called simple or differential power analysis attacks (SPA or DPA). Such attacks comprise the measurement of the power consumption of the integrated circuit during the execution of algorithms handling keys or “secret” quantities that the hacker attempts to discover, this power consumption being different according to the respective states of the bits of the involved data. Power analysis attacks are based on the exploitation of results provided by the chip based on assumptions made on the different bits of the key. Such attacks are generally iterative to successively discover the different bits of a secret quantity.
FIG. 2 shows, in the form of a simplified flowchart, a conventional example of implementation of a modular exponentiation calculation modulo number P, where P is a number over p bits, comprising, based on a message M over any number of bits (coded over at most p bits) and on a secret quantity d over n bits (n being any number), the calculating of result R0=Md mod P (block 20).
To perform this calculation, it is necessary to transit through intermediary results calculated by successive multiplications. It is spoken of a square-multiply method. In the shown example, a single register containing result R is used.
A quantity Rn contained in a single register is initialized (block 21, Rn=1) as being equal to unity. The same register will contain, at the end of an algorithm, final result R0. A counter i is then initialized as being equal to n−1 (block 22). The index i of the counter corresponds to the successive ranks of the n bits of secret quantity d, which may be written as:
  d  =            ∑              i        =        0                    n        -        1              ⁢                  d        i            ⁢                        2          i                ·            
The initialization of index counter i amounts to initializing a loop down to i=0 (block 23), within which successive multiplications will be performed according to the state of current bit di of quantity d.
In a first step (block 24) of the loop, an intermediary result Ri is calculated by squaring up (multiplying by itself) the content of the single register modulo P. Intermediary result Ri=(Ri+1)2 mod P replace the value contained in the result register.
Then, a test (block 25, di=1 ?) of the state of the current bit of quantity d (exponent of the exponentiation) is performed. If this state is 1 (output Y of block 25), the result of the preceding operation is multiplied by message M modulo P (block 26, Ri=Ri*M mod P). The result of this second multiplication is always stored in the same register. If bit di is at state zero (output N of block 25), the operation of block 26 is not executed.
As long as the loop has not ended (output N of block 23), counter i is decremented (block 27, i=i−1) and it is returned to the input of block 24.
At the end of the loop (output Y of block 23), the result register contains quantity R0.
A disadvantage of the method of FIG. 2 is that the circuit power consumption depends on the execution or not of step 26. Now, this execution of step 26 directly depends on the current bit of the quantity meant to remain secret. Accordingly, such an implementation of a modular exponentiation algorithm is particularly vulnerable.